"""
遍历方式，不通过递归
"""

from typing import List, Optional

from tree_node import TreeNode,build_tree_node


class Solution:
    """
    尽量使用迭代法解决问题
    """
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        
        res=[]
        stack=[]
        curr=root
        while stack or curr:
            while curr: # 将左子节点全部压栈
                stack.append(curr)
                curr=curr.left
            curr=stack.pop()
            res.append(curr.val)
            curr=curr.right # 转向右子树

        return res

if __name__=='__main__':
    nums=[1,None,2,3]
    tn=build_tree_node(nums)
    
    sol=Solution()
    res=sol.inorderTraversal(tn)
    print(res)
    pass